package clsFive2;

public class TrieST<Value> {
    private static int R = 256; // 基数
    private Node root;          // 单词查找树的根结点

    private static class Node {
        private Object val;
        private Node[] next = new Node[R];
    }

    public Value get(String key) {
        Node x = get(root, key, 0);
        if (x == null) return null;
        return (Value) x.val;
    }

    private Node get(Node x, String key, int d) {
        // 返回以x作为根结点的子单词查找树中与key相关联的值
        if (x == null) return null;
        if (d == key.length()) return x;
        char c = key.charAt(d); // 找到第d个字符所对应的子单词查找树
        return get(x.next[c], key, d + 1);
    }

    public void put(String key, Value val) {
        root = put(root, key, val, 0);
    }

    private Node put(Node x, String key, Value val, int d) {
        // 如果key存在于以x为根结点的子单词查找树中则更新与它相关联的值
        if (x == null) x = new Node();
        if (d == key.length()) {
            x.val = val;
            return x;
        }
        char c = key.charAt(d); // 找到第d个字符所对应的子单词查找树
        x.next[c] = put(x.next[c], key, val, d + 1);
        return x;
    }
    public static void main(String[] args) {
        TrieST<Integer> trie = new TrieST<>();

        // 插入键值对
        trie.put("apple", 1);
        trie.put("banana", 2);
        trie.put("grape", 3);
        trie.put("orange", 4);
        trie.put("watermelon", 5);

        // 查找键值对
        System.out.println("Value for 'apple': " + trie.get("apple")); // 1
        System.out.println("Value for 'banana': " + trie.get("banana")); // 2
        System.out.println("Value for 'grape': " + trie.get("grape")); // 3
        System.out.println("Value for 'orange': " + trie.get("orange")); // 4
        System.out.println("Value for 'watermelon': " + trie.get("watermelon")); // 5

        // 查找不存在的键
        System.out.println("Value for 'pear': " + trie.get("pear")); // null

        // 更新键值对
        trie.put("apple", 10);
        System.out.println("Updated value for 'apple': " + trie.get("apple")); // 10
    }
}